package bin_tree.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * @author yuisama
 * @date 2023/03/28 21:14
 * 基于int的最大堆
 **/
public class MaxHeap {
    // 具体保存元素的数组
    private List<Integer> data;
    // 堆中有效元素个数
    private int size;
    // heapify =》将任意的整型数组调整为最大堆
    public MaxHeap(int[] arr) {
        this.data = new ArrayList<>(arr.length);
        // 先依次将arr中的每个元素放入堆中
        for (int i : arr) {
            data.add(i);
            size ++;
        }
        // 从当前完全二叉树的最后一个非叶子结点开始向下调整，使得每个子树为堆
        for (int i = parent(size - 1);i >= 0;i --) {
            siftDown(i);
        }

    }


    // 在当前最大堆中取出最大值
    public int extractMax() {
        if (data.isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }
        int val = data.get(0);
        // 1.将当前堆的最后一个元素顶到根节点
        data.set(0,data.get(size - 1));
        data.remove(size - 1);
        size --;
        // 2.从根节点开始向下调整
        siftDown(0);
        return val;
    }
    // 查看当前最大堆的最大值
    public int peekMax() {
        if (data.isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot peek!");
        }
        return data.get(0);
    }


    // 从当前索引为k的位置开始向下调整
    private void siftDown(int k) {
        // 首先保证有子树
        while (leftChild(k) < size) {
            // 判断是否存在右子树且右子树的值比左子树大
            int j = leftChild(k);
            if (j + 1 < size && data.get(j + 1) > data.get(j)) {
                j = j + 1;
            }
            // 此时j索引一定保存了左右子树的最大值~
            if (data.get(k) >= data.get(j)) {
                // 已经下沉到合适位置
                break;
            }else {
                swap(k,j);
                k = j;
            }
        }
    }

    // 向最大堆中添加元素
    public void add(int val) {
        // 1.先尾插新元素到数组的尾部
        this.data.add(val);
        size ++;
        siftUp(size - 1);
    }

    // 元素上浮操作
    private void siftUp(int k) {
        while (k > 0 && data.get(k) > data.get(parent(k))) {
            // 只有当还有父节点且当前节点值 > 父节点时才交换
            swap(k,parent(k));
            // 继续向上判断
            k = parent(k);
        }
    }

    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int capacity) {
            this.data = new ArrayList<>(capacity);
    }
    // 获取父节点
    private int parent(int k) {
        return (k - 1) >> 1;
    }
    // 获取左子树的结点编号
    private int leftChild(int k) {
        return (k << 1) + 1;
    }
    // 获取右子树的结点编号
    private int rightChild(int k) {
        return (k << 1) + 2;
    }


    @Override
    public String toString() {
        return this.data.toString();
    }
}